package data_structure.impl.binaryTree;

/**
 * @Author pedant
 * @Date 2019/8/15 10:32
 * @Description 二叉搜索树
 */
public class SearchTree extends BinaryTree<Integer> {
    public SearchTree() {
        super();
    }

    public SearchTree(Integer[] objs) {
        createBinaryTree(objs);
    }

    /**
     * 重写构建树的方法，二叉搜索树的构造方法如下：
     * 如一个序列：6,5,2,7,8
     * 6作为根节点，5比6小，作为6的左节点，2比6小，也比5小，作为5的左节点
     * 7比6大，作为6的右节点，8比6大，比7大，作为7的右节点
     *
     * @param obj 输入序列
     *            遍历输入序列，依次插入搜索树
     */
    @Override
    protected void createBinaryTree(Object[] obj) {
        for (Object o : obj) {
            insertNode((Integer) o);
        }
    }

    /**
     * 插入节点
     *
     * @param value
     */
    public void insertNode(Integer value) {
        if (root == null) {//递归终止条件
            root = new Node<>(value);
            return;
        }
        insertNode(value, root);//递归找到位置并插入搜索树
    }

    /**
     * 插入一条数据，递归判断插入位置
     *
     * @param node  当前节点
     * @param value
     */
    private Node insertNode(Integer value, Node<Integer> node) {
        if (node == null) {//递归终止条件
            node = new Node<>(value);
            return node;
        }
        if (value <= node.data) {//插入位置在左边
            node.left = insertNode(value, node.left);
        } else {//插入位置在右边
            node.right = insertNode(value, node.right);
        }
        return node;
    }
}
